A trie structure is often used to index ordered data sequences of symbols, such as strings of numbers and/or letters, in a computer system, with at least a portion of the data sequence being stored in nodes in linked lists, each of which pointed to by an entry in the trie that represents one or more starting symbols in the data sequence. Depending on the number of data sequences, the trie can have multiple levels, with the first level representing the first symbol, the second level representing the third level, etc. Typically, a trie is burst to create an additional level when one or more of the linked lists exceed a certain threshold of nodes when new data sequences are added. Levels in the trie can be deleted if the linked lists decrease below the threshold due to the deletion of data sequences.
Because the data sequences can only be accessed through the trie structure, locking mechanisms are employed on the trie structure to avoid simultaneous and conflicting changes being made to the trie structure. As a result, additional processes must be employed to avoid incurring race conditions caused by locking the trie structure.